#ifndef ZL_COLLECTION_LIST
#define ZL_COLLECTION_LIST
#include <string.h>
#include <type_traits>
#include "Interfaces.h"

namespace zl
{
	namespace collections
	{
		
		template<typename T, bool PODType>
		class ListStore :public Object
		{
		};

		template<typename T>
		class ListStore<T, false>:public Object
		{
		protected:
			static void  CopyObjects(T* dest, const T* source, zint count)
			{
				if (dest<source)
				{
					for (zint i = 0; i<count; i++)
					{
						dest[i] = source[i];
					}
				}
				else if (dest>source)
				{
					for (zint i = count - 1; i >= 0; i--)
					{
						dest[i] = source[i];
					}
				}
			}

			static void ClearObjects(T* dest, zint count)
			{
				for (zint i = 0; i<count; i++)
				{
					dest[i] = T();
				}
			}
		public:
		};

		template<typename T>
		class ListStore<T, true>:public Object
		{
		protected:
			static void CopyObjects(T* dest, const T* source, zint count)
			{
				if (count)
				{
					memmove(dest, source, count*sizeof(T));
				}
			}

			static void ClearObjects(T* dest, zint count)
			{

			}
		public:
		};

		template<typename T>
		class ArrayBase :public ListStore<T, std::is_pod<T>::value>
		{
		protected:
			Iterator<T>          _begin;
			Iterator<T>          _end;
			T*                   buffer;
			zint                 count;
		public:
			ArrayBase() :buffer(nullptr), count(0)
			{
				_begin = nullptr;
				_end = nullptr;
			}

			Iterator<T>           begin()const
			{
				return _begin;
			}

			Iterator<T>           end()const
			{
				return _end;
			}

			zint                  size()const
			{
				return count;
			}

			T&              get(zint index)const
			{
				assert(index >= 0 && index < count);
				return buffer[index];
			}

			T&              operator[](zint index)const
			{
				assert(index >= 0 && index < count);
				return buffer[index];
			}
		};

		template<typename T, typename K = typename KeyType<T>::Type>
		class ListBase :public ArrayBase<T>
		{
		protected:
			zint                         capacity_;

			zint                         CalculateCapacity(zint expected)
			{
				zint   result = capacity_;
				while (result<expected)
				{
					result = result * 5 / 4 + 1;
				}
				return result;
			}

			void                          MakeRoom(zint index, zint _count)
			{
				zint  newCount = this->count + _count;
				if (newCount>capacity_)
				{
					zint newCapacity = CalculateCapacity(newCount);
					T*   newBuffer = new T[newCapacity];
					this->CopyObjects(newBuffer, this->buffer, index);
					this->CopyObjects(newBuffer + index + _count, this->buffer + index, this->count - index);
					delete[] this->buffer;
					this->buffer = newBuffer;
					capacity_ = newCapacity;
					this->_begin = this->buffer;
				}
				else
				{
					this->CopyObjects(this->buffer + index + _count, this->buffer + index, this->count - index);
				}
				this->count = newCount;
				this->_end = this->buffer + this->count;
			}

			void                            ReleaseUnnecessaryBuffer(zint previousCount)
			{
				if (this->buffer&&this->count<previousCount)
				{
					this->ClearObjects(&this->buffer[this->count], previousCount - this->count);
				}
				if (this->count <= capacity_ / 2)
				{
					zint  newCapacity = capacity_ * 5 / 8;
					if (this->count<newCapacity)
					{
						T*    newBuffer = new T[newCapacity];
						this->CopyObjects(newBuffer, this->buffer, this->count);
						delete[]this->buffer;
						this->buffer = newBuffer;
						this->_begin = this->buffer;
						capacity_ = newCapacity;
					}
				}
				this->_end = this->buffer + this->count;
			}
		public:
			ListBase()
			{
				this->count = 0;
				capacity_ = 0;
				this->buffer = 0;
			}

			~ListBase()
			{
				delete[]this->buffer;
			}

			zint size()const
			{
				return this->count;
			}

			zint capacity()const
			{
				return this->capacity_;
			}

			bool removeat(zint index)
			{
				zint previousCount = this->count;
				assert(index>=0&&index<this->count);
				this->CopyObjects(this->buffer + index, this->buffer + index + 1, this->count - index - 1);
				this->count--;
				ReleaseUnnecessaryBuffer(previousCount);
				return true;
			}

			bool removerange(zint index, zint _count)
			{
				zint previousCount = this->count;
				assert(index>=0&&index<=this->count);
				assert(index + _count >= 0 && index + _count <= this->count);
				this->CopyObjects(this->buffer + index, this->buffer + index + _count, this->count - index - _count);
				this->count -= _count;
				ReleaseUnnecessaryBuffer(previousCount);
				return true;
			}

			bool clear()
			{
				zint previousCount = this->count;
				this->count = 0;
				capacity_ = 0;
				delete[](this->buffer);
				this->buffer = 0;
				this->_begin = nullptr;
				this->_end = nullptr;
				return true;
			}
		};

		template<typename T, typename K = typename KeyType<T>::Type>
		class Array :public ArrayBase<T>
		{
		public:
			typedef Iterator<T>         iterator;
		protected:
			void                                  Create(zint size)
			{
				if (size > 0)
				{
					this->count = size;
					this->buffer = new T[size];
					this->_begin = this->buffer;
					this->_end = this->buffer + this->count;
				}
				else
				{
					this->buffer = 0;
					this->count = 0;
				}
			}

			void                                   Destory()
			{
				this->count = 0;
				delete[]this->buffer;
				this->buffer = 0;
				this->_begin = nullptr;
				this->_end = nullptr;
			}

		public:
			Array(zint size = 0)
			{
				Create(size);
			}

			Array(const T* _buffer, zint size)
			{
				Create(size);
				this->CopyObjects(this->buffer, _buffer, size);
			}

			Array(const Iterator<T>& __begin, const Iterator<T>& __end)
			{
				zint size = __end - __begin;
				Create(size);
				this->CopyObjects(this->buffer, __begin.obj(), size);
			}

			Array(const Array<T>& _arr)
			{
				zint size = _arr.count;
				Create(size);
				this->CopyObjects(this->buffer,_arr.buffer,size);
			}

			Array(const std::initializer_list<T>& _arr)
			{
				zint size = _arr.size();
				Create(size);
				this->CopyObjects(this->buffer, _arr.begin(), size);
			}

			~Array()
			{
				Destory();
			}

			bool contains(const K& item)const
			{
				return firstindexof(item) != -1;
			}

			zint size()const
			{
				return this->count;
			}

			T& get(zint index)const
			{
				assert(index >= 0 && index < this->count);
				return this->buffer[index];
			}

			T& operator[](zint index)const
			{
				assert(index >= 0 && index < this->count);
				return this->buffer[index];
			}

			zint firstindexof(const K& item)const
			{
				for (zint i = 0; i<this->count; i++)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			zint lastindexof(const K& item)const
			{
				for (zint i = this->count - 1; i >= 0; i--)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			void set(zint index, const T& item)
			{
				assert(index >= 0 && index < this->count);
				this->buffer[index] = item;
			}

			void resize(zint size)
			{
				zint oldCount = this->count;
				T*   oldBuffer = this->buffer;
				Create(size);
				this->CopyObjects(this->buffer, oldBuffer, (this->count<oldCount ? this->count : oldCount));
				delete[]oldBuffer;
			}

			void  clear()
			{
				delete[]this->buffer;
				this->buffer = nullptr;
				this->count = 0;
				this->_begin = nullptr;
				this->_end = nullptr;
			}

			Array<T>&       operator=(const Array<T>& _arr)
			{
				this->clear();
				zint size = _arr.count;
				Create(size);
				this->CopyObjects(this->buffer, _arr.buffer, size);
				return *this;
			}

			Array<T>&        operator=(const std::initializer_list<T>& _right)
			{
				this->clear();
				zint size=_right.size();
				Create(size);
				this->CopyObjects(this->buffer, _right.begin(),size);
				return *this;
			}
		};

		template<typename T, typename K = typename KeyType<T>::Type>
		class List :public ListBase<T, K>
		{
		protected:
			zint indexof(const K& item)const
			{
				for (zint i = 0; i<this->count; i++)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}
		public:
			typedef Iterator<T>         iterator;
		public:
			List()
			{
			}

			List(const Iterator<T>& __begin,const Iterator<T>& __end)
			{
				for (Iterator<T> _it = __begin; _it != __end; _it++)
				{
					this->add(*_it);
				}
			}

			List(const List<T>& _list)
			{
				for (auto i : _list)
				{
					this->add(i);
				}
			}

			List(const std::initializer_list<T>& _list)
			{
				for (auto i : _list)
				{
					this->add(i);
				}
			}

			bool contains(const K& item)const
			{
				return indexof(item) != -1;
			}

			zint firstindexof(const K& item)const
			{
				for (zint i = 0; i<this->count; i++)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			zint lastindexof(const K& item)const
			{
				for (zint i = this->count - 1; i >= 0; i--)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			zint add(const T& item)
			{
				ListBase<T, K>::MakeRoom(this->count, 1);
				this->buffer[this->count - 1] = item;
				return this->count - 1;
			}

			zint insert(zint index, const T& item)
			{
				assert(index >= 0 && index <= this->count);
				ListBase<T, K>::MakeRoom(index, 1);
				this->buffer[index] = item;
				return index;
			}

			bool remove(const K& item)
			{
				zint index = indexof(item);
				if (index == -1) return false;
				while (index >= 0 && index<this->count)
				{
					ListBase<T, K>::removeat(index);
					index = indexof(item);
				}
				return true;
			}

			bool set(zint index, const T& item)
			{
				assert(index >= 0 && index < this->count);
				this->buffer[index] = item;
				return true;
			}

			T& operator[](zint index)const
			{
				assert(index >= 0 && index < this->count);
				return this->buffer[index];
			}

			List<T>&   operator=(const List<T>& right)
			{
				this->clear();
				for (auto i : right)
				{
					this->add(i);
				}
				return *this;
			}

			List<T>&    operator=(const std::initializer_list<T>& right)
			{
				this->clear();
				for (auto i : right)
				{
					this->add(i);
				}
				return *this;
			}

			~List()
			{

			}
		};

		template<typename T, typename K = typename KeyType<T>::Type>
		class SortedList :public ListBase<T, K>
		{
		protected:
			template<typename key>
			zint indexof(const key& item)const
			{
				zint start = 0;
				zint end = this->count - 1;
				while (start <= end)
				{
					zint index = (start + end) / 2;
					if (this->buffer[index] == item)
						return index;
					else if (this->buffer[index]>item)
						end = index - 1;
					else start = index + 1;
				}
				return -1;
			}

			zint indexof(const K& item)const
			{
				return indexof<K>(item);
			}
		public:
			typedef Iterator<T>         iterator;
		public:
			SortedList()
			{

			}

			SortedList(const Iterator<T>& __begin, const Iterator<T>& __end)
			{
				for (Iterator<T> _it = __begin; _it != __end; _it++)
				{
					this->add(*_it);
				}
			}

			SortedList(const SortedList<T>& _list)
			{
				for (auto i : _list)
				{
					this->add(i);
				}
			}

			bool contains(const K& item)const
			{
				return indexof(item) != -1;
			}

			zint firstindexof(const K& item)const
			{
				for (zint i = 0; i<this->count; i++)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			zint lastindexof(const K& item)const
			{
				for (zint i = this->count - 1; i >= 0; i--)
				{
					if (this->buffer[i] == item)
						return i;
				}
				return -1;
			}

			zint add(const T& item)
			{
				if (this->count == 0)
				{
					ListBase<T, K>::MakeRoom(0, 1);
					this->buffer[0] = item;
					return 0;
				}
				else
				{
					zint start = 0;
					zint end = this->count - 1;
					zint index = -1;
					while (start <= end)
					{
						index = (start + end) / 2;
						if (this->buffer[index] == item)
						{
							goto SORTED_LIST_INSERT;
						}
						else if (this->buffer[index]>item)
						{
							end = index - 1;
						}
						else
						{
							start = index + 1;
						}
					}
					assert(index >= 0 && index < this->count);
					if (this->buffer[index]<item)
						index++;
				SORTED_LIST_INSERT:
					ListBase<T, K>::MakeRoom(index, 1);
					this->buffer[index] = item;
					return index;
				}
			}

			bool remove(const K& item)
			{
				zint index = indexof(item);
				if (index == -1) return false;
				while (index >= 0 && index<this->count)
				{
					ListBase<T, K>::removeat(index);
					index = indexof(item);
				}
				return true;
			}

			T& operator[](zint index)const
			{
				assert(index >= 0 && index < this->count);
				return this->buffer[index];
			}

			SortedList<T>&   operator=(const SortedList<T>& right)
			{
				this->clear();
				for (auto i : right)
				{
					this->add(i);
				}
				return *this;
			}

			SortedList<T>&    operator=(const std::initializer_list<T>& right)
			{
				this->clear();
				for (auto i : right)
				{
					this->add(i);
				}
				return *this;
			}

			SortedList<T>&     operator=(List<T>&& right)
			{
				for (auto i : right)
				{
					this->add(i);
				}
				return *this;
			}

		};
	};
};
#endif
